import java.util.LinkedList;
import java.util.Queue;

/*
题目描述：二叉搜索树的第 k 个结点
方法：
中序遍历
 */
public class E54 {
    public static void main(String[] args) {
        TreeNode1 pRoot = new TreeNode1(4);
        pRoot.left = new TreeNode1(2);
        pRoot.left.left = new TreeNode1(1);
        pRoot.left.right = new TreeNode1(3);
        pRoot.right = new TreeNode1(6);
        pRoot.right.left = new TreeNode1(5);
        pRoot.right.right = new TreeNode1(7);

        TreeNode1 res = KthNode(pRoot, 4);

        if(res != null){
            System.out.println(res.val);
        }
    }

    public static TreeNode1 KthNode(TreeNode1 pRoot, int k)
    {
        Queue<TreeNode1> queue = new LinkedList<>();
        if(k == 0){
            return null;
        }
        helper(queue, pRoot);
        for(int i = 0; i < k - 1; i++){
            queue.poll();
        }
        return queue.poll();
    }

    public static void helper(Queue<TreeNode1> queue, TreeNode1 pRoot){
        if(pRoot == null){
            return;
        }
        if(pRoot.left != null){
            helper(queue, pRoot.left);
        }
        queue.add(pRoot);
        if(pRoot.right != null){
            helper(queue, pRoot.right);
        }
    }
}
